package L07.T01;
//判断二叉树是否相同，以及子树判断
//https://leetcode.cn/problems/subtree-of-another-tree/

public class train {
        //判断两个树是否相同
        public boolean isSame(BinaryTree.TreeNode a, BinaryTree.TreeNode b){
            //先对&&进行运算，再对||运算
            //该算法列出了所有的不符合的情况，返回false
            //所有不符合的情况排除，运行到最后一行
            //当左子树和右子树相同时，就是相同的
            if(a==null&&b!=null||a!=null&&b==null)return false;
            if(a==null&&b==null)return true;
            if(a.val!=b.val)return false;
            return isSame (a.left,b.left)&&isSame (a.right,b.right);
        }

        //sub是子的意思
        public boolean isSub(BinaryTree.TreeNode root, BinaryTree.TreeNode subroot) {
            //父节点为空，直接返回false，避免后面的root用空指针进行判断
            if(root==null)return false;
            if (isSame (root, subroot)) return true;
            if (isSub (root.left, subroot)) return true;
            if (isSub (root.right, subroot)) return true;
            //运行到这一行时，说明以上均不满足，返回false
            return false;
        }
}
